package cn.xaut.动态规划;

/**
 * 416. 分割等和子集
 */
public class demo416 {

    /**
     * 时间复杂度：O(n * C)
     * 空间复杂度：O(C)
     * 动态规划
     */
    public boolean canPartition(int[] nums) {

        int n = nums.length;
        if (n == 1)
            return false;

        int sum = 0;
        for (int x : nums)
            sum += x;
        if (sum % 2 == 1)
            return false;
        int C = sum / 2;

        // dp[i] 表示用 nums[0...i] 的数是否能填满容量为 C 的背包
        boolean[] dp = new boolean[C + 1];

        // 基础状态
        for (int i = 0; i <= C; i++)
            dp[i] = i == nums[0];

        // 状态转移
        for (int i = 1; i < n; i++) { 
            for (int j = C; j >= 0; j--) {
                if (j < nums[i])
                    break;
                dp[j] = dp[j] || dp[j - nums[i]];
                if (dp[C])
                    return true;
            }
        }

        return false;
    }

    public boolean canPartition2(int[] nums) {
    
        int sum = 0;
        for (int x : nums)
            sum += x;
        if (sum % 2 != 0)
            return false;
        
        return false;
    }
    
//    private boolean tryPartition(int[] nums, )
    
    public static void main(String[] args) {

        System.out.println(new demo416().canPartition(new int[]{1, 5, 11, 5})); // true
        System.out.println(new demo416().canPartition(new int[]{1, 2, 3, 5})); // false
        System.out.println(new demo416().canPartition(new int[]{1, 5, 3})); // false
    }
}
